COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a121.tex[106,phy] \today\hfill}
\font\rmn=cmr9

\bigskip
\line{\bf Assignment\hfill}

The game of Chomp is played with pieces initially arranged in a rectangle.
The players take turns taking a piece, and all the other pieces that ae
below and/or to the right of~it. The player who takes the last piece
loses. Example game, with a three-column, four-row initial rectangle:

\newbox\bgcrc \setbox\bgcrc=\hbox{$\bigcirc$}
\def\astcirc{\mathop{\hbox to 0pt{\kern-.5pt\raise1pt\hbox to 1\wd\bgcrc{\hfil
	$\ast$\hfil}\hss}\bigcirc}}
%	$\scriptstyle\rightarrow$\hfil}\hss}\bigcirc}}
\bigskip
$$\vcenter{\halign{%
$\hfil#\hfil$\enspace
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\enspace
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\quad
&#\hfil\cr
\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\astcirc%
&\ast&\ast&\ast&\astcirc&\astcirc\cr
\ast&\ast&\ast&\ast&\astcirc&\ast&\ast&&&\ast&&&\ast&&&\astcirc\cr
\ast&\astcirc&\ast&\ast&&&\ast&&&\astcirc\cr
\ast&\ast&\ast&\ast&&&\astcirc\cr
&A&&&B&&&A&&&B&&&A&\multispan2{\hfil $B$}&\multispan2{\hfil $B$}&&B&loses.\cr}}$$

\bigskip\noindent
(In this initial position, if $A$ plays correctly he will win no matter what
$B$ does. Had $A$ made any other initial play, $B$~could have won.

Write an interactive program that plays Chomp, and wins whenever there
is a way to win. It should handle all initial positions up to at least
five columns, eight rows.

Ideas:

\smallskip
\display 20pt:$\bullet$:
The position with no pieces is {\it winning}; your opponent has just taken
the last piece.

\smallskip
\display 20pt:$\bullet$:
A position is {\it losing\/} if every position you can move to is winning;
the one-piece position, for example, is losing.

\smallskip
\display 20pt:$\bullet$:
A position with pieces is {\it winning\/} if you caa move to some losing position.

\smallskip
\display 20pt:$\bullet$:
Think dynamic programming.


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd

First draft December 2, 1987.
%revised: May 6, 1987.
%subsequently revised.

\bye